//二叉查找树
//BST 先要有一个insert() 方法，用来向树中加入新节点。这个方法有点复杂，需要着重讲解。首先要创建一个Node 对象，将数据传入该对象保存。
//    其次检查BST 是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法到此也就完成了；否则，进入下一步。
//
//如果待插入节点不是根节点，那么就需要准备遍历BST，找到插入的适当位置。该过程类似于遍历链表。用一个变量存储当前节点，一层层地遍历BST。
//
//进入BST 以后，下一步就要决定将节点放在哪个地方。找到正确的插入点时，会跳出循环。查找正确插入点的算法如下。
// (1) 设根节点为当前节点。
// (2) 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反之，执行第4 步。
// (3) 如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
// (4) 设新的当前节点为原节点的右节点。
// (5) 如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
//import stack from './stack'

//节点对象
function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
}

Node.prototype = {
    //show方法 返回节点
    show: function () {
        return this.data;
    }
};

//二叉查找树
function BST() {
    this.root = '';
}

BST.prototype = {
    //插入节点
    insert: function (data) {
        var n = new Node(data, '', '');
        if (this.root == '') {
            this.root = n;
        } else {
            var current = this.root;
            var parent;
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.left;
                    if (current == '') {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if (current == '') {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    },
    //中序遍历 即升序遍历 先遍历左子树，再根结点，最后右子树
    //当一个函数被递归调用，在递归没有完成之前，函数的结果会被挂起
    inOrder: function (node) {
        if (node != '') {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    },
    //先序遍历 先访问根结点，然后从左子树到右子树
    preOrder: function (node) {
        if (node != '') {
            console.log(node.show());
            this.preOrder(node.left);
            this.preOrder(node.right);
        }
    },
    //后序遍历 先访问叶子节点，从左子树到右子树，最后根结点
    postOrder: function (node) {
        if (node != '') {
            this.postOrder(node.left);
            this.postOrder(node.right);
            console.log(node.show());
        }
    },
    //非递归中序遍历
    nonRecursiveInOrder: function () {
        const stack = [];
        let node = this.root;
        while (stack.length > 0 || node) {
            if(node){
                stack.push(node);
                node=node.left;
            }else {
                node=stack.pop();
                console.log(node);
                node=node.right;
            }
        }
    }
};